package Examin.WangYi2;

import java.util.*;
public class tu {

    public static int INF = Integer.MAX_VALUE;
    public static int n;
    public static HashMap<Integer, List<Node>> map = new HashMap<Integer, List<Node>>();
    public static boolean[] st;
    public static int[] dist;


    static class Node{
        public int node;
        public int length;

        public Node(int node, int length) {
            this.node = node;
            this.length = length;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int m = scanner.nextInt();

        dist = new int[n + 1];
        st = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            map.put(i, new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int z = scanner.nextInt();
            map.get(x).add(new Node(y,z));
        }
        int max = -1;
        for (int i = 1; i <= n; i++) {
            List<Node> nodes = map.get(i);
            for (Node node : nodes) {
                int y = node.node;
                int z = node.length;
                Node node1 = new Node(i, z);
                map.get(y).add(node1);
                max = Math.max(max,dijkstra());
                map.get(y).remove(node1);
            }
        }
        System.out.println(max);
    }

    private static int dijkstra() {

        for (int i = 1; i <= n; i++) {
            dist[i] = INF;
        }
        dist[1] = 0;
        for (int i = 0; i < n; i++) {
            int t = 0;
            for (int j = 1; j <=n; j++) {
                if(!st[j] && (t==0 || dist[t] > dist[j])){
                    t=j;
                }
            }
            st[t] = true;
            for (Node next : map.get(t)) {
                int j = next.node;
                int len = next.length;
                dist[j] = Math.min(dist[j],dist[t]+len);
            }

        }
        if(dist[n]==INF){
            return -1;
        }
        return dist[n];
    }
}
